//算法思路：
// 使用迭代，将两个链表合并，不占用新空间
// 只使用两个指针，第一个指向起始位，第二个指向较小节点
public class Solution_2 {
    public ListNode mergeTwoLists(ListNode list1head, ListNode list2head) {

        ListNode preHead= new ListNode(-1);
        ListNode prev= new ListNode(-1);

        if(list1head==null)
        {
            return list2head;
        }
        if(list2head==null)
        {
            return list1head;
        }

        prev=preHead;

        while (list1head!=null&&list2head!=null) {
            if (list1head.val <= list2head.val) {
                prev.next = list1head;
                prev=list1head;
                list1head=list1head.next;
            }
            else {
                prev.next=list2head;
                prev=list2head;
                list2head=list2head.next;
            }
        }
        prev.next=list1head==null?list2head:list1head;


        return preHead.next;
    }
}
